import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public String getSmallestString(int n, int k) {
        char[] ret=new char[n];
        Arrays.fill(ret,'a');
        k-=n;
        for(int i=n-1;i>=0;i--){
            if(k<26){
                ret[i]=(char)(k+'a');
                return String.valueOf(ret);
            }
            ret[i]='z';
            k-=25;
        }
        return String.valueOf(ret);
    }
















    public int numIslands(char[][] grid) {
        int ret=0;
        int row=grid.length;
        int col=grid[0].length;
        boolean[][] booleans=new boolean[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'){
                    ret++;
                    dfs(grid,booleans,i,j,row,col);
                }
            }
        }
        return ret;
    }
    public void dfs(char[][] grid,boolean[][] booleans,int x,int y,int row,int col){
        if(x<0||y<0||x>=row||y>=col||grid[x][y]=='0'){
            return;
        }
        grid[x][y]='0';
        dfs(grid,booleans,x+1,y,row,col);
        dfs(grid,booleans,x-1,y,row,col);
        dfs(grid,booleans,x,y+1,row,col);
        dfs(grid,booleans,x,y-1,row,col);
    }


















    public boolean carPooling(int[][] trips, int capacity) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int[] trip:trips){
            int sum =trip[0];
            int start=trip[1];
            int end=trip[2];
            for(int i=start;i<end;i++){
                map.put(i,map.getOrDefault(i,0)+sum);
                if(map.get(i)>capacity){
                    return false;
                }
            }
        }
        return true;
    }



















    public int minSteps(int n) {
        int ret=0;
        for(int i=2;i<n;i++){
            while (n%i==0){
                n/=i;
                ret+=i;
            }
        }
        if(n>1){
            ret+=n;
        }
        return ret;
    }











    public String tree2str(TreeNode root) {
        if(root==null){
            return "";
        }
        if(root.left==null&&root.right==null){
            return root.val+"";
        }
        if(root.right==null){
            return root.val+"("+tree2str(root.left)+")";
        }
        return root.val+"("+tree2str(root.left)+")"+"("+tree2str(root.right)+")";
    }

}
